package com.jieshen.utils;

import com.jieshen.TreeNode;

import java.util.*;

public class BinaryTree {

    /**
     * 根据给定的数组构建二叉树
     * 构建案例:    https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
     *
     * @param arr
     * @return
     */
    public TreeNode BuildTree(Integer[] arr) {
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        if (arr == null || arr.length == 0) {
            return null;
        }
        TreeNode head = new TreeNode(arr[0]);
        nodeQueue.add(head);
        TreeNode pop = null;
        int i = 0;

        while (!nodeQueue.isEmpty()) {
            pop = nodeQueue.remove();
            if (i + 1 < arr.length) {
                i++;
                if (arr[i] != null) {
                    TreeNode left_child = new TreeNode(arr[i]);
                    pop.left = left_child;
                    nodeQueue.add(left_child);
                }
            }
            if (i + 1 < arr.length) {
                i++;
                if (arr[i] != null) {
                    TreeNode right_child = new TreeNode(arr[i]);
                    pop.right = right_child;
                    nodeQueue.add(right_child);
                }
            }
        }
        return head;
    }

    /**
     * 根据二叉树，输出层次遍历的序列
     *
     * @param root
     * @return
     */
    public Integer[] levelOrder(TreeNode root) {
        if (root == null) {
            return new Integer[0];
        }
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.remove();
            list.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        Integer[] arr = new Integer[list.size()];
        int i = 0;
        for (Integer integer : list) {
            arr[i++] = integer;
        }
        return arr;
    }

    public static void main(String[] args) {
        Integer[] arr = {3, 9, 20, null, null, 15, 7};
        BinaryTree tree = new BinaryTree();
        TreeNode treeNode = tree.BuildTree(arr);
        Integer[] AllNodes = tree.levelOrder(treeNode);
        for (Integer allNode : AllNodes) {
            System.out.print(allNode + " ");
        }
        System.out.println();
    }
}
